package com.code.nowcoder;

import java.util.Arrays;
import java.util.Comparator;

/**
 * @author codeDorado
 * @version 1.0
 * @date 2020/7/29 8:45
 */
public class The77_dp {
    /**
     * @param n int整型 ：牛币值种类数
     * @param x int整型 ：牛妹拥有的钱数
     * @param a int整型二维数组 ：第二个vector中的第一列表示币值，第二列表示牛牛拥有币值的个数
     * @return int整型
     * 2,10,[[1, 5],[ 2, 4]]
     * 2
     * 10元可以由 2张1元的和4张2元的组成，也可以由4张1元的和3张2元的组成
     */
    public int solve(int n, int x, int[][] a) {
        // write code here
        // 如果后面的数大于前面的，则交换
        int[][] dp = new int[n + 1][x + 1];
        for (int i = 0; i <= n; i++)
            dp[i][0] = 1;
        for (int i = 1; i <= n; i++) {
            for (int sum = 1; sum <= x; sum++) {
                for (int j = 0;j <= a[i - 1][1] && j * a[i - 1][0] <= sum; j++) {
                    dp[i][sum] += dp[i - 1][sum - j * a[i - 1][0]];
                }
            }
        }
        return dp[n][x];
    }
}
